package interview.recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Combinations
{
	// 第①步：准确定义函数
	/**
	 * Generates all combinations and output them, selecting n elements from data.
	 */
	// 从data里选择数，一共选择n个
	public void combinations(List<Integer> selected, List<Integer> data, int n)
	{
		// initial value for recursion:递归的初始值
		// how to select elements:如何选择0号元素
		// how to output:如何输出

		if (n == 0)
		{
			// output all selected eLements (+ empty list)
			for (Integer i : selected)
			{
				System.out.print(i);
				System.out.print(" ");
			}
			System.out.println();
			return;
		}

		// 判断没有element 0怎么办
		if (data.isEmpty())// 从空集中选取n个元素
		{
			return;// 不输出东西
		}

		// 把递归框架写出来

		// 【情况1：选1】
		// select element 0：选择第0号元素
		selected.add(data.get(0));// 把第0个元素加进去
		// data里剩下的元素(1, data.size())
		// 在剩下的元素中可以选择n-1个元素
		combinations(selected, data.subList(1, data.size()), n - 1);

		// 【情况2：不选1】
		// un-select element 0：不选择第0号元素
		selected.remove(selected.size() - 1);// 把selected里的最后一个元素去掉
		combinations(selected, data.subList(1, data.size()), n);
	}

	public static void main(String[] args)
	{
		// 从[1,2,3,4]里选择2个
		Combinations comb = new Combinations();
		// 调用的时候一个都没选择，所以是new ArrayList<>()
		comb.combinations(new ArrayList<>(), Arrays.asList(1, 2, 3, 4), 2);
		System.out.println("=================");
		// 边缘条件:
		// 从空集里选2个元素
		comb.combinations(new ArrayList<>(), Arrays.asList(), 2);
		System.out.println("=================");
		// 从空集里选0个元素
		comb.combinations(new ArrayList<>(), Arrays.asList(), 0);
		System.out.println("=================");
		// 集合里选1个元素
		comb.combinations(new ArrayList<>(), Arrays.asList(1, 2, 3, 4), 1);
		System.out.println("=================");
		// 集合里选0个元素
		comb.combinations(new ArrayList<>(), Arrays.asList(1, 2, 3, 4), 0);
		System.out.println("=================");
		// 从[1,2,3,4,5,6,7,8,9,10]里取4个元素
		comb.combinations(new ArrayList<>(), Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 4);
	}

}
